This invention relates to parity check codes and, more particularly, to a less resource intensive way for decoding parity check codes using a modified min-sum algorithm.
Electronic information is increasingly being relied upon as a preferred medium for conducting transactions. As a result, demands for even better information storage and/or communication technologies are also increasing. Advances in this area of technology are apparent in telecommunication and information storage devices, where developments in throughput and storage density are allowing users to process information at much greater rates and quantities than before.
To guarantee some degree of information integrity, many communications and storage devices include error-correction technologies. The term “error” as used herein refers to portions of information that have been altered or lost. Error-correction technologies generally involve configuring information in a way that allows the information to be recoverable even when parts of the information are altered or missing. In error-correction, this process of configuring information is referred to as “encoding,” and the counterpart process of recovering information is referred to as “decoding.” Unless otherwise specified, the term “code” will be used herein to refer to a particular way of encoding and decoding information.
Information to be encoded will be referred to herein as “user information,” and the corresponding encoded information will be referred to herein as “coded information.” It is contemplated that user information may have already been previously encoded. User information can be grouped into units called “datawords,” and coded information can be grouped into units called “codewords.” In turn, the datawords and codewords contain symbols, which are groupings of one or more bits. The number of symbols in a dataword is commonly denoted by a variable k, and the number of symbols in a codeword is commonly denoted by a variable n. An encoder generally operates to produce a greater number of codeword symbols than dataword symbols, i.e., generally n>k. A code corresponding to such an encoder is said to have rate-k/n.
One particular type of code is based on a parity check, which is a constraint on the result of a linear sum. For example, suppose a linear sum has the form c1+c2, where c1 and c2 are bits that can each be zero or one. The linear sum is performed in a Galois field GF(q). Since c1 and c2 can only take on values of zero or one, they are GF(2) variables, and the linear sum is performed in GF(2). A parity check enforces a constraint on the result of c1+c2, such as c1+c2=0, for example. Using this exemplary parity check in GF(2), it can be seen that the only combinations of (c1, c2) that satisfy the parity check are (0,0) and (1,1). The combinations (0,1) and (1,0) do not satisfy the parity check because their sums equal one (not zero). The combinations that satisfy a parity check are the codewords of the parity check code. Therefore, the parity check code c1+c2=0 has two codewords (0,0) and (1,1).
A parity check code can guarantee a certain level of information integrity. For example, using the same example above, the combinations (0,1) and (1,0) are not codewords of the parity check code c1+c2=0. Therefore, when coded information includes (0,1) and (1,0), that is an indication that errors have occurred in the coded information. A parity check code decoder can attempt to correct the errors. For example, if a decoder receives information (0,1), the decoder can attempt to determine whether the information more likely corresponds to the codeword (0,0) or the codeword (1,1).
Low-density parity-check (LDPC) codes, a particular class of parity check codes, have superior performance compared to many other types of codes and are widely used in many applications. A LDPC code is a particular type of parity check code in which, generally, there are several parity check constraints and the number of variables in each parity check constraint is relatively small compared to the total number of symbols n in a codeword. Research on parity check code analysis and design often focuses on binary (GF(2)) LDPC codes, even though non-binary (GF(q), q>2) LDPC codes usually perform better, especially on non-binary channels. This is partly due to the fact that the decoder complexity grows very fast with the field size of the code. Existing decoding algorithms either require complex operations or large memory, which can be undesirable. Accordingly, there is continuing interest in using LDPC codes and in developing practical ways to decode LDPC codes.